#include <stdio.h>
#include <stdlib.h>
typedef struct _note {
	int left ;
	int data ;
	int right ;
	struct _note *next ;
}note;
int main(void) {
	int head,n ;
	scanf("%d %d", &head, &n) ;

	note *draft, *d_temp ;
	note *save, *s_temp ;
	note *more, *m_temp ;

	draft = save = more = NULL ;

	//存入数据 
	for(int i=0 ; i<n ; i++) {
		int position ;
		int key ;
		int nxt ;
		scanf("%d %d %d" , &position, &key , &nxt) ;

		note *p = (note *) malloc (sizeof(note*)) ;
		p->left = position ;
		p->data = key ;
		p->right = nxt ;
		p->next = NULL ;

		if(draft==NULL) {
			draft = p ;
			d_temp = draft ;
		} else {
			d_temp->next = p ;
			d_temp = d_temp->next ;
		}

	}

	//这一轮先遍历一遍数据，让其按照正确顺序排序
	int next_one = head ;
	int j=0 ;
	while(j<n) {
		d_temp = draft ;
		while(d_temp) {
			if(d_temp->left==next_one) {
				note *p = (note *) malloc (sizeof(note*)) ;
				p->left = d_temp->left ;
				p->data = d_temp->data ;
				p->right = d_temp->right ;
				p->next = NULL ;
				if(save==NULL) {
					save = p ;
					s_temp = save ;
				} else {
					s_temp->next = p ;
					s_temp = s_temp->next ;
				}
				next_one = s_temp->right ;
				break ;
			}
			d_temp = d_temp->next ;
		}
		if(next_one==-1)
			break ;
		j++ ;
	}
	
	//拆分列表
	int hash[10005] = {0} ;
	s_temp = save ;
	note *s_last = save ;
	while(s_temp) {
		if(hash[abs(s_temp->data)]!=0) {
			s_last->next = s_temp->next ;
			if(more==NULL) {
				more = s_temp ;
				m_temp = more ;
				m_temp->next = NULL ;
			} else {
				m_temp->next = s_temp ;
				m_temp->right = s_temp->left ;
				m_temp = m_temp->next ;
				m_temp->next = NULL ;
			}
			s_temp = s_last->next ;
		} else {
			hash[abs(s_temp->data)] = 1 ;
			s_last = s_temp ;
			s_temp = s_temp->next ;
		}
	}
	s_last->right = -1 ;
	m_temp->right = -1 ;
	
	
	//test
	s_temp = save ;
	while(s_temp) {
		if(s_temp->right==-1)
			printf("%05d %d %d\n" , s_temp->left , s_temp->data , s_temp->right) ;
		else
			printf("%05d %d %05d\n" , s_temp->left , s_temp->data , s_temp->next->left) ;
		s_temp = s_temp->next ;
	}
	//test
	m_temp = more ;
	while(m_temp) {
		if(m_temp->right==-1)
			printf("%05d %d %d\n" , m_temp->left , m_temp->data , m_temp->right) ;
		else
			printf("%05d %d %05d\n" , m_temp->left , m_temp->data , m_temp->right) ;
		m_temp = m_temp->next ;
	}

	return 0 ;
}